Transactions on Combinatorics
Volume:11 Issue: 2, Jun 2022

Peripheral Hosoya polynomial of a graph $G$ is defined as‎,‎ begin{align*}‎‎ &PH(G,lambda)=sum_{kgeq 1}d_P(G,k)lambda^k,\‎‎ text{where $d_P(G,k)$ is the number} &text{ of pairs of peripheral vertices at distance $k$ in $G$.}‎‎ end{align*}‎Peripheral Hosoya polynomial of composite graphs viz.‎, ‎$G_1times G_2$ the Cartesian product‎, ‎$G_1+G_2$ the join‎, ‎$G_1[G_2]$ the composition‎, ‎$G_1circ G_2$ the corona and $G_1{G_2}$ the cluster of arbitrary connected graphs $G_1$ and $G_2$ are computed and their peripheral Wiener indices are stated as immediate consequences‎.

The modified bubble-sort graph $MB_n$ $(n geq 2)$ has been known as a topology structure of interconnection networks‎. ‎In this paper‎, ‎we propose simple method for arc-transitivity of $MB_n$ $(n geq 2)$‎. ‎Also by using this result we investigate some reliability measures‎, ‎including‎ ‎super-connectivity‎, ‎cyclic edge connectivity‎, ‎etc.‎, ‎in the modified bubble-sort graphs‎.

An optimal labeling of a graph with $n$ vertices and $m$ edges is an injective assignment of the first $n$ nonnegative integers to the vertices‎, ‎that induces‎, ‎for each edge‎, ‎a weight given by the sum of the labels of its end-vertices with the property that the set of all induced weights consists of the first $m$ positive integers‎. ‎We explore the connection of this labeling with other well-known functions such as super edge-magic and $alpha$-labelings‎. ‎A graph with $n$ vertices is maximal when the number of edges is $2n-3$; all the results included in this work are about maximal graphs‎. ‎We determine the number of optimally labeled graphs using the adjacency matrix‎. ‎Several techniques to construct maximal graphs that admit an optimal labeling are introduced as well as a family of outerplanar graphs that can be labeled in this form.

Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman ${3}$-domination. A function $g : V(G) rightarrow lbrace 0, 1, 2, 3 rbrace$ having the property that $sum_{v in N_G(u)}^{} g(v) geq 3$, if $g(u) = 0$, and $sum_{v in N_G(u)}^{} g(v) geq 2$, if $g(u) = 1$ for any vertex $u in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an textit{ independent Roman ${3}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = sum_{v in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman ${3}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $lbrace 3 rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.

The unitary Cayley graph $Gamma_n$ of a finite ring $mathbb{Z}_n$ is the graph with vertex set $mathbb{Z}_n$ and two vertices $x$ and $y$ are adjacent if and only if $x-y$ is a unit in $mathbb{Z}_n$‎. ‎A family $mathcal{F}$ of mutually edge disjoint trees in $Gamma_n$ is called a tree cover of $Gamma_n$ if for each edge $ein E(Gamma_n)$‎, ‎there exists a tree $Tinmathcal{F}$ in which $ein E(T)$‎. ‎The minimum cardinality among tree covers of $Gamma_n$ is called a tree covering number and denoted by $tau(Gamma_n)$‎. ‎In this paper‎, ‎we prove that‎, ‎for a positive integer $ ngeq 3 $‎, ‎the tree covering number of $ Gamma_n $ is $ displaystylefrac{varphi(n)}{2}+1 $ and the tree covering number of $ overline{Gamma}_n $ is at most $ n-p $ where $ p $ is the least prime divisor of $n$‎. ‎Furthermore‎, ‎we introduce the Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of rings $mathbb{Z}_n$‎.